/*
  This is an example code.
  It doesn't do much of the thing,
  and I don't think you should copy it.

  (BTW, it's just my C programming Language
  homework. )

  The purpose of this code is to expand
  a abbrevation to its full format:

  Example:
    + 1-9 => 123456789
    + 1-2-5 => 12345
    + a-b1-3 => ab123
 */

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define EXP_MAX_LEN 16
#define MAX_EXP 16
#define MAX_STACK 24

/*
  Syntax of expand:
  <exp> ::= <head> '-' <tail> [<exp>]
  <head> ::= <alphabet>
  <tail> ::= <exp> | <alphabet>
  <alphabet> ::= [0-9] | [a-z]

  To Parse the syntax:
  1. read char, if match head?
  + no, break and return '\0'
  + yes, do step 2
  2. read char, if match '-'?
  + no, break and throw error
  + yes, do step 3
  3. make a [head, ...],
  in which ... stands for '\0'
  redo 1

  So the AST would be something like a
  linked list:

  [head, [head, [head, '\0']]]

  However, not knowing how to make a array
  in c contain another array, I think
  I should just flatten the linked list:

  [[head_a1, head_a2, ...], [head_b1, ...]]

  To eval the AST:
  1. get head, test if tail
  + no tail, end
  + has tail, do step 2
  2. add to res until tails head
  redo step 1
  Ok, this is my way. 
*/

void expand(char *input, char *output);
int read(char *input, char **ast);
char *read_exp(char *input, char *out_ast_exp);
int test_alphabet(char c);
void eval(char **ast, int size, char *output);
void print_ast(char **ast, int n); // for debug usage

int main() {
  char *input;
  char *output;
  input = (char *)malloc(EXP_MAX_LEN);
  output = (char *)malloc(MAX_STACK);

  printf("Input: ");
  scanf("%s", input);
  expand(input, output);

  printf("the input: %s is expanded to: \n", input);
  printf("%s\n", output);
}

void expand(char *input, char *output) {
  int n;
  char **stack;
  stack = (char **)malloc(MAX_EXP);
  // Note: it is bad, though I don't know how to improve
  for (int i = 0; i < MAX_EXP; i++)
    *(stack + i) = (char *)malloc(MAX_EXP);

  n = read(input, stack);
  // print_ast(stack, n); // print out the ast
  eval(stack, n, output);
}

int read(char *input, char **ast) {
  int i = 0;

  while (*input != '\0') {
    // *(ast + i) = (char *)malloc(MAX_EXP);
    input = read_exp(input, *(ast + i));
    i++;
  }
  
  return i;
}

char *read_exp(char *input, char *out_ast_exp) {
  int read_head = TRUE;

  while (*(input) != '\0') {
    if (read_head && test_alphabet(*input)) {
      read_head = FALSE;
      *(out_ast_exp++) = *input;
    }else if (!read_head && *input == '-') {
      read_head = TRUE; 
    } else if (!read_head && test_alphabet(*input)){
      *(out_ast_exp) = '\0';
      return input;
    } else {
      puts("Error when read exp. \n");
      puts("Tracing back: \n");
      printf("`... %s'\n", input);
      exit(0);
    }

    input++;
  }

  *(out_ast_exp) = '\0';
  return input;
}

// TRUE if c in [0-9a-zA-Z]
int test_alphabet(char c) {
  return (('0' <= c && c <= '9')
	  || ('a' <= c && c <= 'z')
	  || ('A' <= c && c <= 'Z'))
    ? TRUE : FALSE;
}

void eval(char **ast, int size, char *output) {
  int i = 0, j = 0;
  while (j < size) { // each exp in ast
    *(output++) = **(ast+j);

    while (*(*(ast+j) + i + 1) != '\0') { // each head i
      for (char c = *(*(ast+j) + i) + 1; c <= *(*(ast+j) + i + 1); c++) {
	*(output++) = c;
      }
      i++;
    }

    i = 0;
    j++;
  }
  *(output) = '\0';
}

void print_ast(char **ast, int n) {
  for (int i = 0; i < n; i++)
    printf("[%s]", *(ast+i));
}
